//
//  42. 接雨水.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/5/16.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation

class Solution42 {
    // 采用单调栈
    // 记录的是元素的index
    func trap(_ height: [Int]) -> Int {
        guard height.count >= 3 else {
            return 0
        }
        var stack: [Int] = []
        var totalCount = 0
        for i in 0..<height.count {
            while !stack.isEmpty && height[i] > height[stack.last!] {
                let last = stack.removeLast()
                if !stack.isEmpty {
                    let minH = min(height[stack.last!], height[i])
                    totalCount += ((minH - height[last]) * (i - stack.last! - 1))
                }
            }
            stack.append(i)
        }
        return totalCount
    }
    static func test(){
        let solution = Solution42()
        let height = [0,1,0,2,1,0,1,3,2,1,2,1]
        let result = solution.trap(height)
        print(result)
    }
}
